/**
 * Created with IntelliJ IDEA.
 * Description :
 * User: $ {USER}
 * Date: $ {YEAR}-$ {MONTH}一$ { DAY}
 * Time: ${ TIME}
 */

/**
 * 题目：回文链表
 * 思路：和正常判断回文数一样，我们首先得让left指针指向链表的头和right指向链表的尾，
 *      就开始遍历链表即可。但链表是单链表不能反向遍历，因此突破点就是把链表反转即可
 *      反转链表就是用快慢指针去遍历遍历链表，找到中间位置开始反转即可
 */
public class Test {
    public boolean isPalindrome(ListNode head) {
        // 题目明确说明了节点个数不为空，因此无需判断
        // 利用快慢指针走到中间节点的位置
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 开始反转后半部分的结点
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
            if (curNext != null) {
                curNext = curNext.next;
            }
        }
        // 开始从两头遍历
        fast = head;
        while (slow != fast && fast.next != slow) {
            if (slow.val != fast.val) {
                return false;
            }
            slow = slow.next;
            fast = fast.next;
        }
        // 比较相邻的情况
        return fast.val == slow.val;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}